//
//  46. 全排列 46. 全排列 46_全排列.swift
//  Swift-LeetCode
//
//  Created by 卢悦明 on 2024/3/14.
/**
 https://leetcode.cn/problems/permutations/description/
 给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

  

 示例 1：

 输入：nums = [1,2,3]
 输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
 示例 2：

 输入：nums = [0,1]
 输出：[[0,1],[1,0]]
 示例 3：

 输入：nums = [1]
 输出：[[1]]

 */

import UIKit
// 优化
class QuanPailie: NSObject {
    
    
    func QA() {
       print(permute([1, 2, 3]))
    }
    
    func permute(_ nums: [Int]) -> [[Int]] {
        if nums.count == 0 { return [] }
        var results = [[Int]]()
        dps(0, nums, &results)
        return results
    }
    
    func dps(_ index: Int, _ nums: [Int], _ resluts: inout [[Int]]) {
        if index == nums.count {
            let temp = Array(nums)
            resluts.append(temp)
            return
        }
        
        for i in index..<nums.count {
            var tempArray = nums
            (tempArray[i], tempArray[index]) = (tempArray[index], tempArray[i])
            dps(index + 1, tempArray, &resluts)
        }
    }
    
    
}

class QuanPailie1: NSObject {
    
    
    func QA() {
       print(permute([1, 2, 3]))
    }
    
    func permute(_ nums: [Int]) -> [[Int]] {
        if nums.count == 0 { return [] }
        var results = [[Int]]()
        var array = [Int]()
        dps(0, nums, &results, &array)
        return results
    }
    
    func dps(_ index: Int, _ nums: [Int], _ resluts: inout [[Int]], _ array: inout [Int]) {
        if index == nums.count {
            let temp = Array(array)
            resluts.append(temp)
            return
        }
        
        for item in nums {
            if array.contains(item) { continue }
            array.append(item)
            dps(index + 1, nums, &resluts, &array)
            array.removeLast()
        }
    }
    
    
}


